/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package util.sorting;

import saphre.core.Store;

import java.util.Arrays;
import util.sedgewick.StdRandom;


/**
 * Code adapted from original from Sedgewick, Algorithms in Java, 3rd ed.
 * The code in the 4th edition is easier to understand but considerably less optimized.
 * Copyright © 2000–2011, Robert Sedgewick and Kevin Wayne.
 * 
 */
public class RadixQSort {

    int[] corpus;
    int sentinel;
    int N;
    public static boolean verbose = false;
    public static Store store;

    
    public RadixQSort(int[] corpus, Store aStore) {
        this.corpus = corpus;
        this.store = aStore;
        this.N = corpus.length;
        this.sentinel = corpus[corpus.length - 1];
    }

    public RadixQSort(int[] corpus) {
        this.corpus = corpus;
        this.N = corpus.length;
        this.sentinel = corpus[corpus.length - 1];
    }

    static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public void sort(int[] suftab, int lo, int hi) {
        StdRandom.shuffle(suftab, 1, N - 2);
        sort(suftab, lo, hi, 0);
    }

    // Use n-2 because n-1 is for the final sentinel, which
    // doesn't need to be sorted
    // rx.sort(result,1,n-2,0);
    // rx.sort(result);
    public void sort(int[] suftab) {
        // StdRandom.shuffle(suftab,1,N - 2);
        sort(suftab, 1, N - 2, 0);
    }

    public void sort(int[] a, int lo, int hi, int d) {
        if (hi <= lo) {
            return;
        }
        int i = lo - 1, j = hi;
        int p = lo - 1, q = hi;
        int v = corpus[a[hi] + d];

        while (i < j) {

            while (corpus[a[++i] + d] < v) {
                ; /* if (i == hi) break; */
            }
            while (v < corpus[a[--j] + d]) {
                if (j == lo) {
                    break;
                }
            }

            if (i > j) {
                break;
            }
            exch(a, i, j);
            if (corpus[a[i] + d] == v) {
                exch(a, ++p, i);
            }
            if (corpus[a[j] + d] == v) {
                exch(a, j, --q);
            }
        }
        if (p == q) {
            if (v != sentinel) {
                //vpr("1. " + v + " " + sentinel + " " + (d + 1));
                sort(a, lo, hi, d + 1);
                return;
            }
        }
        if (corpus[a[i] + d] < v) {
            i++;
        }

        for (int k = lo; k <= p; k++) {
            exch(a, k, j--);
        }

        for (int k = hi; k >= q; k--) {
            exch(a, k, i++);
        }
        //vpr("2. " + lo + " " + j + " " + d);
        sort(a, lo, j, d);
        if ((i == hi) && (corpus[a[i] + d] == v)) {
            i++;
        }

        if (v != sentinel) {
            //vpr("3." + (d + 1));
            sort(a, j + 1, i - 1, d + 1);
        }
        //vpr("4. " + lo + " " + j + " " + d);
        sort(a, i, hi, d);
    }

    
    public static void vpr(String s) {
        if (verbose) {
            System.out.println(s);
        }
    }

    public static void main(String[] args) {

        // TEXT:
        // 0123456789........18=g,19=$,20=$
        // mining_engineering    <- original lexicographic.
        // $mining_engineering$$  <- original with sentinels.

        // 
        // eeegggiiiimnnnnnr_     <- help sorted lexicographic.
        // 000111222234444456     <- help sorted transcribed.
        // 324241634124005241     <- lexicographic, transcribed.

        // 9 324241604124005241 7 8 <- original with end markers.

        // SUFFIX ARRAY:
        // 0 13 8 14 10 6 18 11 4 16 2 1 12 9 5 17 3 15 7 19 20
        //   

        // lexicogaphically sorted.
        // 13 - eering$
        // 8  - engineering$
        // 14 - ering$
        // 10 - gineering$
        // 6  - g_engineering$
        // 18 - g$
        // ..
        // 15 - ring
        // 7 - _engineering
        // 19



        //int[] corN = {4, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 3};
        // corresponds to 
        // $mining_engineering$$
        int[] unsorted = {9, 3, 2, 4, 2, 4, 1, 6, 0, 4, 1, 2, 4, 0, 0, 5, 2, 4, 1, 7, 8};
        int n = unsorted.length;

        RadixQSort rx = new RadixQSort(unsorted);

        int[] w = new int[n];
        for (int i = 1; i < n; i++) {
            w[i] = i;
        }
        vpr(Arrays.toString(w));

        System.out.println(Arrays.toString(w));

        rx.sort(w, 1, n - 2, 0);
        //rx.sort(w);

        vpr(Arrays.toString(w));
        // The lexicographically sorted suffixes.
        // 0 13 8 14 10 6 18 11 4 16 2 1 12 9 5 17 3 15 7 19 20
        System.out.println(Arrays.toString(w));

        int[] sorted = {0, 13, 8, 14, 10, 6, 18, 11, 4, 16, 2, 1, 12, 9, 5, 17, 3, 15, 7, 19, 20};

    }
}
